1. Field of the Invention
The present invention relates to a system for retrieving a destination address, to which a packet will be transmitted, and more particularly to a destination retrieving system realizing a desired high speed retrieving process for retrieving a destination address, to which a packet with plural headers will be transmitted.
All of patents, patent applications, patent publications, scientific articles and the like, which will hereinafter be cited or identified in the present application, will, hereby, be incorporated by references in their entirety in order to describe more fully the state of the art, to which the present invention pertains.
2. Description of the Related Art
Destination retrieving systems have been used for designating or deciding one or more destinations, to which one or more packets will be transmitted, based on contents described in a packet header. Examples of the conventional destination retrieving systems are disclosed in Japanese laid-open patent publication No. 11-187024, and Japanese laid-open patent publication No. 2000-244571, as well as Japanese laid-open patent publication No. 2000-151709.
Typical one of the conventional destination retrieving systems will, hereinafter, be described with reference to the drawings. FIG. 1 shows the typical one of the conventional destination retrieving systems. The conventional destination retrieving system includes a packet buffer 100, a destination address retrieving unit 110, a destination address information storage unit 120, a packet receiving unit 130, a packet transmitting unit 140, and a central processing unit 150.
The packet receiving unit 130 receives a destination-undecided packet, for which a decision to a destination address has not yet been made but the decision is needed for transmitting the packet. The packet buffer 100 is functionally coupled to the packet receiving unit 130 for receiving the packet from the packet receiving unit 130 and storing the packet therein. The packet buffer 100 comprises a storage unit for storing the packet received by the packet receiving unit 130.
The packet transmitting unit 140 is functionally coupled to the packet buffer 100 for receiving the packet from the packet buffer 100. The packet transmitting unit 140 is also functionally coupled to the central processing unit 150. The packet transmitting unit 140 is capable of transmitting a destination-decided packet, for which a decision to the destination address for transmission has already been made. The packet transmitting unit 140 is also capable of transferring, to the central processing unit 150, a destination-undecidable packet, for which any decision to destination address for packet transmission could not be made.
The destination address retrieving unit 110 is functionally coupled to the packet buffer 100 for making a decision of a destination address of the destination-undecided packet stored in the packet buffer 100. The destination address retrieving unit 110 is further functionally coupled to the packet receiving unit 130 and also to the packet transmitting unit 140. The destination address information storage unit 120 is functionally coupled to the destination address retrieving unit 110. The destination address information storage unit 120 may store a plurality of destination address information table which enables the destination address retrieving unit 110 to retrieve a destination address for the destination-undecided packet stored in the packet buffer 100 based on the destination address information table. The central processing unit 150 is functionally coupled to the packet buffer 100. The central processing unit 150 processes only a destination-undecidable packet, for which any decision to destination address for packet transmission could not be made by the destination address retrieving unit 110. The process is executed in accordance with a given program.
The destination address retrieving unit 110 has an internal function-block structure shown in FIG. 2. As described above, the destination address retrieving unit 110 is functionally coupled to the packet buffer 100, the destination address information storage unit 120, the packet receiving unit 130 and the packet transmitting unit 140. The destination address retrieving unit 110 includes a packet-header-extracting/retrieving-method-deciding unit 111, a table-selecting/destination-retrieving unit 112 and a packet header converting unit 113.
The packet-header-extracting/retrieving-method-deciding unit 111 is functionally coupled to the packet receiving unit 130 for receiving a destination address retrieving instruction from the packet receiving unit 130. The packet-header-extracting/retrieving-method-deciding unit 111 is also functionally coupled to the packet buffer 100 for extracting a packet header from the packet stored in the packet buffer 100, so that the packet-header-extracting/retrieving-method-deciding unit 111 decides a packet type from the packet header. A location and a size of the destination address as well as the number of necessary informations such as addresses for deciding the destination are variable depending upon the packet type. For this reason, the packet-header-extracting/retrieving-method-deciding unit 111 previously decides a location and a size of the destination address as well as the number and extraction location of the other necessary informations for enabling the table-selecting/destination-retrieving unit 112 to perform table-selecting and destination-retrieving processes based on those informations. The retrieving method is represented by those retrieving-purpose informations necessary for the destination address retrieval. Thus, the retrieving method corresponds to retrieval keys, based on which the table-selecting/destination-retrieving unit 112 performs the destination-retrieving process. Typical examples of the existent packet types are Internet Protocol version 4 (IPv4), Internet Protocol version 6 (IPv6) and Multiprotocol Label Switching.
The table-selecting/destination-retrieving unit 112 is functionally coupled to the packet-header-extracting/retrieving-method-deciding unit 111 for receiving, from the packet-header-extracting/retrieving-method-deciding unit 111, the retrieving-purpose informations including the packet type and the address of the packet header. The table-selecting/destination-retrieving unit 112 is also functionally coupled to the destination address information storage unit 120 which stores a plurality of destination address information table. The table-selecting/destination-retrieving unit 112 selects a destination address information table 121 based on the designated retrieving method from the plurality of destination address information table stored in the destination address information storage unit 120.
As described above, the retrieving method is designated or decided by the packet-header-extracting/retrieving-method-deciding unit 111 based on the packet type designated in the packet header given from the packet buffer 100. Namely, the table-selecting/destination-retrieving unit 112 selects the destination address information table 121 based on the packet type or the designated retrieving method. The table-selecting/destination-retrieving unit 112 performs retrieval of a destination address for the packet based on the selected destination address information table 121.
The packet header converting unit 113 is functionally coupled to the table-selecting/destination-retrieving unit 112 for receiving the retrieved destination address as well as the header and the packet type from the table-selecting/destination-retrieving unit 112. The packet header converting unit 113 is also functionally coupled to the packet buffer 100 for performing an editorial process for the header based on the retrieved destination address and a header-renewal process for renewing the header necessary for the packet transmission of the packet stored in the packet buffer 100. The packet header converting unit 113 is also functionally coupled to the packet transmitting unit 140 for sending a packet transmission instruction to the packet transmitting unit 140 after the both editorial and renewal processes described above have been completed.
Operations of the above-described conventional destination retrieving system of FIGS. 1 and 2 will subsequently be described with reference to FIG. 3.
In step 200, after the packet receiving unit 130 has received a destination-undecided packet, then the packet receiving unit 130 transfers the received destination-undecided packet to the packet buffer 100, so that the packet buffer 100 stores the packet therein. The packet receiving unit 130 also sends a destination address retrieving instruction to the destination address retrieving unit 110.
In step 210, the packet-header-extracting/retrieving-method-deciding unit 111 receives the destination address retrieving instruction from the packet receiving unit 130. In accordance with the destination address retrieving instruction, the packet-header-extracting/retrieving-method-deciding unit 11 extracts a packet header from the packet stored in the packet buffer 100, so that the packet-header-extracting/retrieving-method-deciding unit 111 decides a packet type from the packet header. The packet-header-extracting/retrieving-method-deciding unit 111 sends the packet type and the address of the packet header to the table-selecting/destination-retrieving unit 112.
In step 220, the table-selecting/destination-retrieving unit 112 selects a destination address information table 121 based on the address from the plurality of destination address information table stored in the destination address information storage unit 120. The table-selecting/destination-retrieving unit 112 retrieves a destination address for the packet based on the selected destination address information table 121.
In step 230, after the retrieval of the destination address has been completed, then the packet header converting unit 113 receives the retrieved destination address from the table-selecting/destination-retrieving unit 112 as well as receives the header and the packet type from the packet-header-extracting/retrieving-method-deciding unit 111. The packet header converting unit 113 performs an editorial process for the header based on the retrieved destination address and a header-renewal process necessary for renewing the header necessary for the packet transmission of the packet stored in the packet buffer 100. The packet header converting unit 113 sends a packet transmission instruction to the packet transmitting unit 140 after the both editorial and renewal processes described above have been completed.
In accordance with the packet transmission instruction from the packet header converting unit 113, the packet transmitting unit 140 transmits the packet stored in the packet buffer 100 to the destination address. If the destination address of the packet could not be decided or designated by the destination address retrieving unit 110, then the packet stored in the packet buffer 100 is processed by the central processing unit 150 in accordance with a program.
In the meantime, the packets be classified into a first type packet which has a single-stage header structure and a second type packet which has a multi-stage header structure. FIG. 4A is a view of the first type packet with the single-stage header structure. FIG. 4B is a view of the second type packet with the multi-stage header structure. As shown in FIG. 4A, a first type packet 300 has a single header 301 which needs a decision of any destination address. As shown in FIG. 4B, a second type packet 310 has both internal and external headers 312 and 311 which need decisions of respective destination addresses, wherein the internal header 312 is capsuled with the outer header 311, while the outer header 311 capsules the internal header 312.
FIG. 5 is a diagram of a plurality of first-type network, over which address of the internal header is effective, and a single second-type network, over which address of the external header is effective. Address of the internal header 312 is effective over the first-type networks 410, 420 and 430. Address of the internal header 311 is effective over the second type network 400. The packet 300 with the single stage header 301 is effective over the first-type networks 410, 420 and 430 only. The packet 310 with the internal and external headers 312 and 311 is effective over not only the first-type networks 410, 420 and 430 but also the second-type network 400. Packet switches 415, 425 and 435 are provided between the second-type network 400 and the first-type networks 410, 420 and 430 respectively. Each of the packet switches 415, 425 and 435 is capable of capsuling or de-capsuling the external header 311 onto or from the internal header 312 for enabling the packet to be effective over the second-type network 400 or the first-type networks 410, 420 and 430.
The above-described conventional destination retrieving system is effective only to perform a high speed process for deciding or designating the destination address for the single-stage packet 300 which has the single header 301 which needs a decision of any destination address. The above-described conventional destination retrieving system is, however, ineffective in view of high speed processes for the multi-stage packet 310 because each of the packet switches 415, 425 and 435.
FIG. 6 is a flow chart of operations of the packet switch for capsuling or de-capsuling the external header onto or from the internal header for enabling the packet to be effective over the second-type network or the first-type networks shown in FIG. 5. Each of the packet switches 415, 425 and 435 is capable of capsuling the external header 311 onto the internal header 312 for enabling the packet to be effective over the second-type network 400 or de-capsuling the external header 311 from the internal header 312 for enabling the packet to be effective over the first-type networks 410, 420 and 430. The following operations by each of the packet switches 415, 425 and 435 is implemented by the central processing unit 150 shown in FIG. 1.
In step 500, the central processing unit 150 decides whether or not the received packet is the packet transmitted from the second type network 400, over which the address of the external header is effective.
In step 510, if the central processing unit 150 has made a decision to the effect that the received packet is not the packet transmitted from the second type network 400, the central processing unit 150 retrieves the contents of the internal header.
In step 520, the central processing unit 150 decides whether or not the packet is needed to be transferred to the second type network 400, over which the address of the external header is effective.
In step 540, if the central processing unit 150 decides that the packet is not needed to be transferred to the second type network 400, then the central processing unit 150 transfers the packet to the first type network 410, 420 or 430.
In step 530, if the central processing unit 150 decides that the packet is needed to be transferred to the second type network 400, then the central processing unit 150 capsules or adds the external header to the packet.
In step 580, the central processing unit 150 transfers the packet with the external header to the second type network 400.
In step 550, if the central processing unit 150 has made another decision to the effect that the received packet is the packet transmitted from the second type network 400, the central processing unit 150 retrieves the contents of the external header.
In step 560, the central processing unit 150 decides whether or not the packet is needed to be transferred to the first type network 410, 420 or 430, over which the address of the internal header is effective.
In step 580, if the central processing unit 150 decides that the packet is not needed to be transferred to the first type network 410, 420 or 430, then the central processing unit 150 transfers the packet to the second type network 400.
In step 570, if the central processing unit 150 decides that the packet is needed to be transferred to the first type network 410, 420 or 430, then the central processing unit 150 de-capsules or deletes the external header from the packet.
In step 580, the central processing unit 150 transfers the packet with the external header to the first type network 410, 420 or 430.
In general, the last-mentioned process by the central processing unit 150 to the packet is remarkably slower than the above-mentioned process by the destination address retrieving unit 110. If the packet has the single-stage header structure or the single header, then the destination address retrieving unit 110 is capable of retrieving the destination address. If the packet has the plural-stage header structure or the plural headers, then the destination address retrieving unit 110 is incapable of retrieving the destination address, and the central processing unit 150 is needed to perform the processes described above and with reference to FIG. 6.
Consequently, the above-described conventional destination retrieving system is incapable of high speed process for retrieving a destination address for a packet which has a plurality of header.
In the above circumstances, the development of a novel destination retrieving system free from the above problems is desirable.